1. Field of the Invention
The present invention relates to a method, apparatus and computer program product for edge detection suitable for both natural as well as noisy images that includes a novel algorithm.
2. Prior Art
One of the most intensively studied problems in computer vision concerns with how to detect edges in images. Edges are important since they mark the locations of discontinuities in depth, surface orientation, or reflectance. Edges and fibers constitute features that can support segmentation, recognition, denoising, matching and motion analysis tasks.
Accurate detection of edges, discussed supra, can be challenging, particularly when low contrast edges appear in the midst of noise. FIG. 1 shows electron microscope images that demonstrate the challenge of detecting edges (at different scales) embedded in noise. The images in FIG. 1, acquired by an electron microscope, exemplify this kind of challenge. FIG. 2 shows two adjacent noisy intensity profiles (right) parallel to a long edge (left) in an image acquired by electron microscope.
Despite the noise (see profile plots in FIG. 2), such low contrast edges are evident to the human eye due to their consistent appearance over lengthy curves. Accurate handling of low contrast edges is useful also in natural images, where boundaries between objects maybe weak due to similar reflectance properties on both sides of an edge, shading effects, etc.
Common algorithms for edge detection (e.g., J. Canny. A computational approach to edge detection. TPAMI, 8:679-698, 1986. 2) overcome noise by applying a preprocessing step of smoothing, typically using a gaussian kernel of a user specified width. Scale-space representations extend this approach, allowing for a simultaneous delineation of edges from all scales by combining spatially varying gaussian smoothing with automatic scale selection [see T. Lindeberg. Edge detection and ridge detection with automatic scale selection. CVPR, page 465, 1996. 2, and M. Tabb and N. Ahuja. Multiscale image segmentation by integrated edge and region detection. IEEE, Trans. on Image Processing, 6(5):642-655, 1997. 2].
A related approach was designed for fiber enhancement in medical applications [A. Frangi, W. Niessen, K. Vincken, and M. Viergever. Multiscale vessel enhancement filtering. LNCS, 1496:130-137, 1998. 2]. Such isotropic smoothing, however, often reduces the contrast of weak edges, may blend adjacent edges, and may result in poor localization of edges.
To avoid the pitfalls of isotropic smoothing, anisotropic diffusion schemes [such as P. Perona and J. Malik. Scale space and edge detection using anisotropic diffusion. TPAMI, 12(7):629-639, 1990. 2; J. Weickert. A review of nonlinear diffusion filtering. Scale-Space Theory in Computer Vision, LNCS, 1252:3-28, 1997. 2; and R. Kimmel, R. Malladi, and N. Sochen. Images as embedded maps and minimal surfaces: Movies, color, texture, and volumetric medical images. IJCV, 39:111-129, 2000. 2] were proposed as a means for edge-preserving smoothing and image enhancement. These methods utilize a diffusion tensor designed to avoid smoothing in the direction of the intensity gradients, while allowing smoothing in coherence directions. These approaches improve edge localization considerably, and edges at different scales are revealed at different iterations of the diffusion process. These edges remain visible in their original location for many iterations before they finally fade out. A scale selection mechanism however is required to extract edges of different scales. As the reliance on local gradients in traditional diffusion processes may lead to accumulation of noise, recent methods, as noted, above modify the diffusion tensor through isotropic spatial averaging or resetting of its eigen-values. Such spatial smoothing and eigen-value modifications are, however, adapted to a single scale. Moreover, by using an averaged diffusion tensor, these methods accumulate squared local intensity differences, and this may lead to smoothing across noisy, low contrast edges. The reliance on local gradients is a common problem also in both single and multiscale variational methods [see D. Mumford and J. Shah. Optimal approximation by piecewise smooth functions and associated variational problems. Comm. on Pure Applied Math., 42:577-685, 1989. 2; and X. Bresson, P. Vandergheynst, and J. Thiran. Multiscale active contours. IJCV, 70(3):197-211, 2006. 2].
Another stream of work utilizes filters of various lengths, widths, and orientation, yielding curvelet and contourlet image decomposition [see J. Starck, F. Murtagh, E. Candes, and D. Donoho. Gray and color image contrast enhancement by the curvelet transform. IEEE, Trans. on Image Processing, 12(6):706-717, 2003. 2; M. Do and M. Vcttcrli. The contourlet transform: an efficient directional multiresolution image representation. IEEE, Trans on Image Processing, 14(12):2091-2106, 2005. 2; and S. Kalitzin, B. I H. Romeny, and M. Vierger. Invertible apertured orientation filters in image analysis. IJCV, 31(2), 1999. 2].
The focus of these methods, however, is mainly on achieving sparse representations of images and not on edge extraction or fiber enhancement. Finally, recent methods for edge detection in natural images [see M. Ruzon and C. Tomasi. Edge, junction, and corner detection using color distributions. TPAMI, 23(11): 1281-1295, 2001. 2 and D. Maitin, C. Fowlkes, and 3. Malik. Learning to detect natural image boundaries using local brightness, color, and texture cues. TPAMI, 26(5):530-548, 2004. 2, 6] compare histograms of intensity, color (and also texture in D. Maitin et al) in two half disks on either sides of an edge, while in M Ruzon et al the size of the disc is related to the length of the edges. While this approach avoids smoothing across a measured edge, the use of large discs may lead to smoothing across nearby edges. Furthermore, the histograms are calculated at all locations and orientations leading to inefficient schemes.